A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets. The packets are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
Certain devices, referred to as routers, maintain routing information that describes routes through the network. A “route” can generally be defined as a path between two locations on the network. Conventional routers often maintain the routing information in the form of one or more routing tables or other data structures. The form and content of the routing tables often depend on the particular routing algorithm implemented by the router.
Upon receiving incoming packets, the routers examine information within the packets, and forward the packets in accordance with the routing information. In order to maintain an accurate representation of the network, routers periodically exchange routing information in accordance with routing protocols, such as the Border Gateway Protocol (BGP).
When two network devices that are BGP peers (or neighbors) initially connect, the BGP peers typically exchange routing information specifying one or more routes. From then on, the BGP peers send control messages to incrementally update the routing information when the network topology changes. For example, the BGP peers may send update messages to advertise newly available routes and withdraw routes that are no longer available.
A BGP router frequently receives unwanted routes from its peers that the BGP router then drops in accordance with a local routing policy. For example, in some cases peers of a BGP router may send route advertisements to the BGP router announcing routes that the BGP router would not utilize according to its local routing policy. In order to save network resources involved in generating, sending, receiving, and processing routing messages containing unwanted routing information updates, a BGP router may send an outbound route filter (ORF), in the form of one or more ORF entries, to each of its BGP peers, which the BGP peers then use to filter outbound routes for that router. Each ORF includes ORF entries that specify the action for the BGP peers to take upon a route match, typically “deny” or “permit,” and the ORF entries are stored by BGP routers in a separate list for each BGP peer. When determining whether to filter outbound routes for a BGP peer, a BGP router consults the corresponding ORF for that BGP peer. The BGP router compares outbound routes to the ORF entries of the corresponding ORF to determine the appropriate ORF entry to apply to the outbound routes being advertised. A BGP-based mechanism that allows a BGP router to send to its BGP peer an ORF, in the form of one or more ORF entries, that the peer would use to constrain/filter its outbound route updates to the router is defined in Chen, E., and Rekhter, Y., “Outbound Route Filtering Capability for BGP-4”, draft-ietf-idr-route-filter-15.txt, July 2006, hereby incorporated by reference.
Further, one ORF-type for BGP, termed “Address Prefix Outbound Route Filter (Address Prefix ORF)”, that can be used to perform address prefix based route filtering is defined in “Address Prefix Based Outbound Route Filter for BGP-4”, by Chen, E., and Sangli, S., draft-ietf-idr-bgp-prefix-orf-04.txt, January 2007, hereby incorporated by reference. An address prefix-based ORF consists of an sequence of address-prefix ORF entries, each of which defines the range of route prefixes and route prefix lengths to which the filter applies, as well as the action to be taken on finding a match.
Use of such address prefix-based route filters has become common by network providers to implement local policy-based route filtering for inbound or outbound routes. In order to determine whether to accept or reject a route, a router determines the action for the prefix-based route filter with the smallest sequence number in the list matching the route prefix. Inefficient implementations of route filter list require traversal of the entire list for determining the match, which can degrade routing performance significantly.